By Julian Hautzmayer k11904007
In this notebook I tested four different minimization techniques:
For simplification all used code is extracted to different .py files:
pls have a look at the implementation as here you will only see the result and conclusion.
import main # from this script I trigger all methods with examples
import methods as m
First I use my implementations of steepest descent, newton method, quasi newton and linear conjugate gradient to solve 5 randomly generated quadratic objective functions.
For every random generated example all four methods are applied. For every applied method we start from a random point and make a number of iterations. Here you can see how in every case the loss decreases and converges. After all iterations you can see which point was reached.
At the end we want to see if our result really found a minimum. Therefore we plug in the steps we took in the gradient and see that again in every case the gradient converges against 0 proving that we indeed found a minimum in every case. After every method run with an example this can be seen in the plot.
main.test_all_qof_methods()
Now I will apply every of my 5 predefined functions to every single minimization algorithm I implemented. You will see similar metrics like above, but now additionally you will see the true minima of the predefined function and a plot showing the steps of the algorithm. From this you can clearly see that every method was able to reach every single minima of every single predefined function.
If a predefined function has multiple minima, I tried to hit all of them.
Sometimes a function e.g. steepest descent takes a lot longer but in the end every single method reaches its target in a reasonable bound of error. All the meta data of the methods used and the defined starting points can be found in main.py.
For every single run of a method you can see a plot. The red dot (which is sometimes not visiable any more because my solution is right on top) are the true minimum, the blue star is the start, the green star is my solution and the red line with yellow dots is the path the algorithm took.
main.test_method(m.steepest_descent, 'steepest descent', main.meta_steepest_descent)
main.test_method(m.newton, 'newton', main.meta_newton)
main.test_method(m.quasi_newton, 'quasi newton', main.meta_quasi_newton)
main.test_method(m.non_linear_conjugate_gradient, 'conjugate gradient', main.meta_conjugate_gradient)